// ++++++++++++++++++++++++++++++++++++++++
// 《零基础Go语言算法实战》源码
// ++++++++++++++++++++++++++++++++++++++++
// Author:廖显东（ShirDon）
// Blog:https://www.shirdon.com/
// Gitee:https://gitee.com/shirdonl/goAlgorithms.git
// Buy link :https://item.jd.com/14101229.html
// ++++++++++++++++++++++++++++++++++++++++

package main

import (
	"fmt"
	"math"
)

// 定义一个包含 x 和 y 坐标的 Point 结构体
type Point struct {
	x int
	y int
}

// 创建一个空切片来保存N皇后问题问题的结果
var results = make([][]Point, 0)

// 找到N皇后问题问题的所有可能解
func nQueenSolve(n int) {
	// 遍历每一列
	for col := 0; col < n; col++ {
		// 为当前列创建一个起点
		start := Point{x: col, y: 0}
		// 创建一个空切片来保存当前解决方案
		current := make([]Point, 0)
		// 从当前列开始递归解决问题
		Recurse(start, current, n)
	}
	// 打印结果
	fmt.Print("结果:\n")
	for _, result := range results {
		fmt.Println(result)
	}
	// 打印找到的解决方案总数
	fmt.Printf("一共有 %d 解决方法\n", len(results))
}

// 从指定点开始递归求解N皇后问题
func Recurse(point Point, current []Point, n int) {
	// 如果当前点是板上的有效位置，则将其添加到当前解决方案中
	if CanPlace(point, current) {
		current = append(current, point)
		// 如果当前解包含 n 个点，则将其添加到结果列表中
		if len(current) == n {
			c := make([]Point, n)
			for i, point := range current {
				c[i] = point
			}
			results = append(results, c)
		} else {
			// 否则，从下一行的每个点开始递归求解
			for col := 0; col < n; col++ {
				for row := point.y; row < n; row++ {
					nextStart := Point{x: col, y: row}
					Recurse(nextStart, current, n)
				}
			}
		}
	}
}

// 确定是否可以在不攻击任何其他棋子的情况下将目标点放在棋盘上
func CanPlace(target Point, board []Point) bool {
	for _, point := range board {
		if CanAttack(point, target) {
			return false
		}
	}
	return true
}

// 判断棋盘上的两点是否可以互相攻击
func CanAttack(a, b Point) bool {
	// 如果两个点在同一行、同一列或对角线上，则它们可以相互攻击
	answer := a.x == b.x || a.y == b.y ||
		math.Abs(float64(a.y-b.y)) == math.Abs(float64(a.x-b.x))
	return answer
}

func main() {
	nQueenSolve(4)
}

//$ go run nQueen.go
//结果:
//[{1 0} {3 1} {0 2} {2 3}]
//[{2 0} {0 1} {3 2} {1 3}]
//一共有 2 解决方法
